{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Student Attendance Record II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkRecord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #学生出勤记录 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：\n",
    "<ul>\n",
    "\t<li><code>'A'</code>：Absent，缺勤</li>\n",
    "\t<li><code>'L'</code>：Late，迟到</li>\n",
    "\t<li><code>'P'</code>：Present，到场</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果学生能够 <strong>同时</strong> 满足下面两个条件，则可以获得出勤奖励：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>按 <strong>总出勤</strong> 计，学生缺勤（<code>'A'</code>）<strong>严格</strong> 少于两天。</li>\n",
    "\t<li>学生 <strong>不会</strong> 存在 <strong>连续</strong> 3 天或 <strong>连续</strong> 3 天以上的迟到（<code>'L'</code>）记录。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，表示出勤记录的长度（次数）。请你返回记录长度为 <code>n</code> 时，可能获得出勤奖励的记录情况 <strong>数量</strong> 。答案可能很大，所以返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：\n",
    "</strong>有 8 种长度为 2 的记录将被视为可奖励：\n",
    "\"PP\" , \"AP\", \"PA\", \"LP\", \"PL\", \"AL\", \"LA\", \"LL\" \n",
    "只有\"AA\"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10101\n",
    "<strong>输出：</strong>183236316\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [student-attendance-record-ii](https://leetcode.cn/problems/student-attendance-record-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [student-attendance-record-ii](https://leetcode.cn/problems/student-attendance-record-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '1', '10101']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A') >= 2:\n",
    "            return False\n",
    "        if 'LLL' in s:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absents=lates=0\n",
    "        #枚举的意思，把s字符串里面的字符存入i和c,i存储的是下标，c存储的是字母\n",
    "        for i,c in enumerate(s):\n",
    "            if c ==\"A\":\n",
    "                absents+=1\n",
    "                if absents>=2:\n",
    "                    return False\n",
    "            if c==\"L\":\n",
    "                lates+=1\n",
    "                if lates>=3:\n",
    "                    return False\n",
    "            else:\n",
    "                    lates=0\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        n = \"PPALLL\"\n",
    "        ii = 'LLL'\n",
    "        if ii not in s and s.count('A')<2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and not 'LLL' in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A')<2 and 'LLL' not in s:\n",
    "            return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and (\"LLL\" not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.find('LLL') == -1 and s.count('A') < 2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if \"LLL\" in s:\n",
    "            return False\n",
    "        s_list = list(s)\n",
    "        if s_list.count('A') >= 2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "\n",
    "        if s.count('A')>=2:\n",
    "            return False    \n",
    "        elif 'LLL' in s:   \n",
    "            return False    \n",
    "        else:\n",
    "            return True    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and s.find('LLL')<0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return False if 'LLL'in s or s.count('A')>1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        A_count = s.count('A')\n",
    "        if A_count >= 2:\n",
    "            return False\n",
    "        L_count = 0\n",
    "        for str in s:\n",
    "            if str != 'L':\n",
    "                if L_count >= 3:\n",
    "                    return False\n",
    "                L_count = 0\n",
    "            else:\n",
    "                L_count += 1\n",
    "        if L_count >= 3:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent_count = 0\n",
    "        late_count = 0\n",
    "\n",
    "        for record in s:\n",
    "            if record == 'A':\n",
    "                absent_count += 1\n",
    "                late_count = 0\n",
    "                if absent_count >= 2:\n",
    "                    return False\n",
    "            elif record == 'L':\n",
    "                late_count += 1\n",
    "                if late_count >= 3:\n",
    "                    return False\n",
    "            else:\n",
    "                late_count = 0\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        late = 0\n",
    "        absent = 0\n",
    "        for i in s:\n",
    "            if i==\"A\":\n",
    "                absent+=1\n",
    "                late=0\n",
    "            elif i==\"L\":\n",
    "                late+=1\n",
    "                if late>=3:\n",
    "                    return False\n",
    "            else:\n",
    "                late=0\n",
    "        return True if absent<2 else False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        latecount=0\n",
    "        absentcount=0\n",
    "        arr=list(s)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]=='A':\n",
    "                absentcount+=1\n",
    "            if i<=len(arr)-3 and arr[i]==arr[i+1]==arr[i+2]=='L':\n",
    "                latecount+=3\n",
    "        if absentcount<2 and latecount<3:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return 'LLL' not in s and s.count('A') < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') <= 1 and \"LLL\" not in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return True if \"LLL\" not in s and s.count(\"A\") < 2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and s.find('LLL') == -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        cnt_a=0\n",
    "        c_cnt_l=0\n",
    "        last_ch=''\n",
    "        for ch in s:\n",
    "            if ch=='A':\n",
    "                cnt_a+=1\n",
    "                if cnt_a>=2:\n",
    "                    return False\n",
    "            elif ch=='L':\n",
    "                if last_ch=='L':\n",
    "                    c_cnt_l+=1\n",
    "                    if c_cnt_l>=3:\n",
    "                        return False\n",
    "                else:\n",
    "                    c_cnt_l=1\n",
    "            last_ch=ch\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A')<2 and 'LLL' not in s:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        late_count = 0\n",
    "\n",
    "        for i in s:\n",
    "            if i == 'A':\n",
    "                absent += 1\n",
    "                late_count = 0\n",
    "            elif i == 'L':\n",
    "                late_count += 1\n",
    "            elif late_count != 0:\n",
    "                late_count =0\n",
    "            \n",
    "            if absent == 2 or late_count == 3:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and 'LLL' not in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        countCharacters={}\n",
    "        for i in s:\n",
    "            if i not in countCharacters:\n",
    "                countCharacters[i]=1\n",
    "            else:\n",
    "                countCharacters[i]+=1\n",
    "        if \"A\" not in s and \"LLL\" not in s:\n",
    "            return True\n",
    "        elif \"A\" in s and countCharacters[\"A\"]<2 and \"LLL\" not in s:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        cntA = cntL = 0\n",
    "        for x in s:\n",
    "            match x:\n",
    "                case 'A':\n",
    "                    cntA += 1\n",
    "                    if cntA == 2:\n",
    "                        return False\n",
    "                    cntL = 0\n",
    "                case 'L':\n",
    "                    cntL += 1\n",
    "                    if cntL == 3:\n",
    "                        return False\n",
    "                case _:\n",
    "                    cntL = 0\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A') < 2 and 'LLL' not in s:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s):\n",
    "        return 'LLL' not in s and s.count('A') < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if(s.count('A') >= 2):\n",
    "            return False\n",
    "        if(s.count(\"LLL\") != 0):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if(s.count('A') >= 2):\n",
    "            return False\n",
    "        if(s.count(\"LLL\") != 0):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and ( 'LLL' not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        return cnt['A'] < 2 and 'LLL' not in s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and 'LLL' not in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and s.count('LLL') ==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return not 'LLL' in s and s.count('A') < 2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        abscnt = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] =='A':\n",
    "                abscnt +=1\n",
    "                if abscnt >=2:\n",
    "                    return False\n",
    "            elif s[i] =='L':\n",
    "                if i-1>=0 and i+1<len(s): \n",
    "                    if s[i-1] =='L' and s[i+1] =='L':\n",
    "                        return False \n",
    "        return True                  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkRecord(self, s: str) -> bool:\r\n",
    "        return self.valid2A(s) and self.valid3L(s)\r\n",
    "        \r\n",
    "    def valid2A(self,s : str):\r\n",
    "        count = 0\r\n",
    "        for c in s:\r\n",
    "            if c == 'A':\r\n",
    "                count += 1\r\n",
    "        return count < 2\r\n",
    "\r\n",
    "    def valid3L(self,s : str):\r\n",
    "        if s.find('LLL') == -1 :\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            return False\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A') >= 2:\n",
    "            return False\n",
    "        for day in range(0,len(s)-2):\n",
    "            if s[day:day+3] == 'LLL':\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        #return s.count('A')<2 and not 'LLL' in s\n",
    "        #计数枚举\n",
    "        absents=lates=0\n",
    "        for i,num in enumerate(s):\n",
    "            if num=='A':\n",
    "                absents+=1\n",
    "                if absents>=2:\n",
    "                    return False\n",
    "            if num=='L':\n",
    "                lates+=1\n",
    "                if lates>=3:\n",
    "                    return False\n",
    "            else:#如果不是连续三天L就置0\n",
    "                lates=0\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and not 'LLL' in s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if(s.count('A') < 2 and s.count(\"LLL\") == 0):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        absent = 0\n",
    "        if s.count('A') >= 2:\n",
    "            return False\n",
    "        if 'LLL' in s:\n",
    "            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        late_count = 0\n",
    "\n",
    "        for i in s:\n",
    "            if i == 'A':\n",
    "                absent += 1\n",
    "                late_count = 0\n",
    "            elif i == 'L':\n",
    "                late_count += 1\n",
    "            elif late_count != 0:\n",
    "                late_count =0\n",
    "            \n",
    "            if absent == 2 or late_count == 3:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        late_count = 0\n",
    "\n",
    "        for i in s:\n",
    "            if i == 'A':\n",
    "                absent += 1\n",
    "                late_count = 0\n",
    "            elif i == 'L':\n",
    "                late_count += 1\n",
    "            elif late_count != 0:\n",
    "                late_count =0\n",
    "            \n",
    "            if absent == 2 or late_count == 3:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent,late = 0,0\n",
    "        for i,c in enumerate(s):\n",
    "            if c=='A':\n",
    "                absent += 1\n",
    "                if absent >= 2:\n",
    "                    return False\n",
    "            if c=='L':\n",
    "                late += 1\n",
    "                if late >= 3:\n",
    "                    return False\n",
    "            else:\n",
    "                late = 0\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if 'LLL' in s:\n",
    "            return False\n",
    "        elif s.count('A')>=2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A') >= 2:\n",
    "            return False\n",
    "        else:\n",
    "            flg = 0\n",
    "            for i in s:\n",
    "                if i == 'L':\n",
    "                    flg += 1\n",
    "                    if flg >= 3:\n",
    "                        return False\n",
    "                else:\n",
    "                    flg = 0\n",
    "            return True \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        d = collections.Counter(s)\n",
    "        aflag = False\n",
    "        lflag = False\n",
    "        if d['A'] < 2:\n",
    "            aflag = True\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'L' and i < len(s) - 2:\n",
    "                if s[i + 1] == 'L' and s[i + 2] == 'L':\n",
    "                    lflag = True\n",
    "                    break\n",
    "        return aflag and (not lflag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return 'LLL' not in s and s.count('A') < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and s.count('LLL') ==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        a_count=0\n",
    "        l_count=0\n",
    "        for c in s:\n",
    "            if c=='L':\n",
    "                l_count+=1\n",
    "                if l_count>=3:\n",
    "                    return False\n",
    "            else:\n",
    "                l_count=0               \n",
    "                if c=='A':\n",
    "                    a_count+=1\n",
    "                    if a_count>=2:\n",
    "                        return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return not 'LLL' in s and s.count('A') < 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if(s.count(\"A\")<2 and s.count(\"LLL\")==0):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and 'LLL' not in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        late_count = 0\n",
    "\n",
    "        for i in s:\n",
    "            if i == 'A':\n",
    "                absent += 1\n",
    "                late_count = 0\n",
    "            elif i == 'L':\n",
    "                late_count += 1\n",
    "            elif late_count != 0:\n",
    "                late_count =0\n",
    "            \n",
    "            if absent == 2 or late_count == 3:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkRecord(self, s: str) -> bool:\r\n",
    "        s_list = list(s)\r\n",
    "        if s_list.count('A') < 2 and 'LLL' not in s:\r\n",
    "            return True\r\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count('A')<2 and 'LLL' not in s:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        k=s.count(\"A\")\n",
    "        n=len(s)\n",
    "        if n==2 and k==2:\n",
    "            return False\n",
    "        elif n<=1:\n",
    "            return True\n",
    "        for i in range (n-2):\n",
    "            if s[i]==s[i+1]==s[i+2]==\"L\" or  k>=2:\n",
    "                return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        l=0\n",
    "        a=0\n",
    "        for i in s:\n",
    "            if l>=3:\n",
    "                return False\n",
    "            if i==\"A\":\n",
    "                a+=1\n",
    "                l=0\n",
    "            elif i==\"L\":\n",
    "                l+=1\n",
    "            else:\n",
    "                l=0\n",
    "        if a<2 and l<3:\n",
    "            return True\n",
    "        else:\n",
    "            return False    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and 'LLL' not in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absents = lates = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"A\":\n",
    "                absents += 1\n",
    "                if absents >= 2:\n",
    "                    return False\n",
    "            if c == \"L\":\n",
    "                lates += 1\n",
    "                if lates >= 3:\n",
    "                    return False\n",
    "            else:\n",
    "                lates = 0\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        Late = 0\n",
    "        if s[0] == 'A':\n",
    "            absent += 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == 'A':\n",
    "                absent += 1\n",
    "                if absent >= 2:\n",
    "                    return False\n",
    "            elif s[i] == 'L' and s[i-1] == 'L':\n",
    "                Late += 1\n",
    "                if Late >= 2:\n",
    "                    return False\n",
    "            else:\n",
    "                Late = 0\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        count1=0\n",
    "        count2=0\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return True\n",
    "        if n==2:\n",
    "            if s[0]==s[1]=='A':\n",
    "                return False\n",
    "            return True\n",
    "        if n>2:\n",
    "            if s[0]=='A':\n",
    "                count1+=1\n",
    "            if s[1]=='A':\n",
    "                count1+=1 \n",
    "            for i in range(2,n):\n",
    "                if s[i]=='A':\n",
    "                    count1+=1\n",
    "                if s[i-2]==s[i-1]==s[i]=='L':\n",
    "                    count2+=1\n",
    "            if count1<2 and count2==0:\n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        list_s=list(s)\n",
    "        count=list_s.count('A')\n",
    "        if count>=2 or 'LLL' in s:\n",
    "            return False\n",
    "        if count<2 and 'LLL' not in s:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A') < 2 and ('LLL' not in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        A_count=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='A':\n",
    "                A_count+=1\n",
    "                if A_count==2:\n",
    "                    return False\n",
    "            if i<len(s)-2 and s[i]=='L' and s[i+1]=='L' and s[i+2]=='L':\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return s.count('A')<2 and 'LLL' not in s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        return not 'LLL' in s and s.count('A') < 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absent = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'A':\n",
    "                absent += 1\n",
    "                if absent == 2: return False\n",
    "            elif s[i] == 'L':\n",
    "                if s[i:i+3] == 'LLL': return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        if s.count(\"A\") > 1 or \"LLL\" in s:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, s: str) -> bool:\n",
    "        absents = 0\n",
    "        lates = 0\n",
    "        #reward = True\n",
    "        for ch in s:\n",
    "            if ch == 'A':\n",
    "                absents += 1\n",
    "                if absents >= 2:\n",
    "                    return False\n",
    "            if ch == 'L':\n",
    "                lates += 1\n",
    "                if lates >= 3:\n",
    "                    return False\n",
    "            else:\n",
    "                lates = 0\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        f=[[[0]*3 for _ in range(2)] for _ in range(2)]\n",
    "        f[0][0][0]=1\n",
    "        for i in range(1,n+1):\n",
    "            for A in range(2):\n",
    "                for L in range(3):\n",
    "                    if L==0:\n",
    "                        f[i%2][A][0]=(f[(i-1)%2][A][0]+f[(i-1)%2][A][1]+f[(i-1)%2][A][2])%mod\n",
    "                        if A==1:\n",
    "                            f[i%2][A][0]=(f[i%2][A][0]+f[(i-1)%2][A-1][0]+f[(i-1)%2][A-1][1]+f[(i-1)%2][A-1][2])%mod\n",
    "                    else:\n",
    "                        f[i%2][A][L]=f[(i-1)%2][A][L-1]%mod\n",
    "\n",
    "                            \n",
    "        ans=0\n",
    "        for a in range(2):\n",
    "            for b in range(3):\n",
    "                ans=(ans+f[n%2][a][b])%mod\n",
    "        return ans%mod\n",
    "                \n",
    "\n",
    "                    \n",
    "        \n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,A,L):\n",
    "        #     if A>=2 or L>=3:\n",
    "        #         return 0\n",
    "        #     if i<=0:\n",
    "        #         return 1\n",
    "        #     a=dfs(i-1,A+1,0)\n",
    "        #     b=dfs(i-1,A,L+1)\n",
    "        #     c=dfs(i-1,A,0)\n",
    "        #     return (a+b+c)\n",
    "        # return dfs(n,0,0)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dp = [0] * 100000\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        A = 1\n",
    "        P = [1,0]\n",
    "        L = [1,0]\n",
    "        LL = [0,0]\n",
    "        if self.dp[n-1]:\n",
    "            return self.dp[n-1]\n",
    "\n",
    "        for i in range(100000):\n",
    "            if i:\n",
    "                a =  P[0]+L[0]+LL[0]\n",
    "\n",
    "                p0 = P[0]+L[0]+LL[0]\n",
    "                p1 = A+P[1]+L[1]+LL[1]\n",
    "                \n",
    "                l0 = P[0]\n",
    "                l1 = A+P[1]\n",
    "\n",
    "                ll0 = L[0]\n",
    "                ll1 = L[1] \n",
    "                \n",
    "                A = a\n",
    "                P = [p0,p1]\n",
    "                L = [l0,l1]\n",
    "                LL =[ll0,ll1]\n",
    "\n",
    "                self.dp[i] =  (A+sum(P)+sum(L)+sum(LL))%(10 ** 9 + 7)\n",
    "            else:\n",
    "                self.dp[i] = 3\n",
    "\n",
    "        return self.dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        pre, tmp, MOD = [1, 0, 0], [1], 1000000007\n",
    "        \n",
    "        for i in range(n):\n",
    "            pre[0], pre[1], pre[2] = sum(pre) % MOD, pre[0], pre[1]\n",
    "            tmp.append(sum(pre) % MOD)\n",
    "\n",
    "        return (tmp[n] + sum([tmp[i] * tmp[n - i - 1] % MOD for i in range(n)])) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # 特殊处理只有1天的情况\n",
    "        if n == 1:\n",
    "            return 3\n",
    "        # L[i] 表示第 i 天为迟到的情况下并且不存在缺勤情况下的奖励数目\n",
    "        L = [1] * (n + 1)\n",
    "        # P[i] 表示第 i 天为出勤的情况下并且不存在缺勤情况下的奖励数目\n",
    "        P = [1] * (n + 1)\n",
    " \n",
    "        mod = int(1e9+7)\n",
    "        for i in range(2, n + 1):\n",
    "            # 可以连续迟到1天或者2天\n",
    "            L[i] = (P[i-1] + P[i-2]) % mod\n",
    "            # 前一天可以迟到也可以出勤\n",
    "            P[i] = (L[i-1] + P[i-1]) % mod\n",
    "        # 首先 L[n] + P[n]肯定是满足要求的，因为L[n] P[n] 不存在缺勤或者迟到超过2天\n",
    "        # 第一个L[n-1] + P[n-1]表示第一天缺勤，其他n-1天都不缺勤\n",
    "        # 第二个L[n-1] + P[n-1]表示第n天缺勤，前n-1天都不缺勤\n",
    "        ans = (L[n] + P[n] + L[n-1] + P[n-1] + L[n-1] + P[n-1]) % mod\n",
    "        # i表示第i天缺勤，此时所贡献的答案为（前i-1 天不缺勤总数）* （后n-i天不缺勤总数） \n",
    "        for i in range(2,n):\n",
    "            ans = (ans + (L[i-1] + P[i-1]) * (L[n-i] + P[n-i])) % mod\n",
    "        return ans % mod\n",
    "s = Solution()\n",
    "s.checkRecord(10101)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Induction rule:\n",
    "# P[n] = P[n-1] + L[n-1] + A[n-1]\n",
    "# L[n] = P[n-1] + A[n-1] + P[n-2] + A[n-2]\n",
    "# A[n] = A[n-1] + A[n-2] + A[n-3]\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        if n == 1: return 3\n",
    "        if n == 2: return 8\n",
    "\n",
    "        P = [0 for _ in range(n)]\n",
    "        L = [0 for _ in range(n)]\n",
    "        A = [0 for _ in range(n)]\n",
    "\n",
    "        P[0] = L[0] = A[0] = 1\n",
    "        P[1] = L[1] = 3\n",
    "        A[1] = 2\n",
    "        A[2] = 4\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        for i in range(1, n):\n",
    "            P[i-1] %= mod\n",
    "            L[i-1] %= mod\n",
    "            A[i-1] %= mod\n",
    "\n",
    "            P[i] = ((P[i-1] + L[i-1])%mod + A[i-1])%mod\n",
    "            if i > 1:\n",
    "                L[i] = (((P[i-1] + A[i-1])%mod + P[i-2])%mod + A[i-2])%mod\n",
    "            if i > 2:\n",
    "                A[i] = ((A[i-1] + A[i-2])%mod + A[i-3])%mod\n",
    "        \n",
    "        return ((P[n-1] + L[n-1])%mod + A[n-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp_p=[0]*(n+1)\n",
    "        dp_l1=[0]*(n+1)\n",
    "        dp_l2=[0]*(n+1)\n",
    "        dp_a=[0]*(n+1)\n",
    "        dp_p[1]=dp_l1[1]=dp_l2[0]=dp_a[1]=1\n",
    "        M=10**9+7\n",
    "        for i in range(2,n+1):\n",
    "            dp_p[i]=(dp_p[i-1]+dp_l1[i-1]+dp_l2[i-1])%M\n",
    "            dp_l1[i]=dp_p[i-1]\n",
    "            dp_l2[i]=dp_l1[i-1]\n",
    "            dp_a[i]=dp_p[i]\n",
    "            # print('#',i)\n",
    "            # print(dp_p)\n",
    "            # print(dp_l1)\n",
    "            # print(dp_l2)\n",
    "            # print(dp_a)\n",
    "        for i in range(2,n+1):\n",
    "            dp_p[i]=(dp_p[i-1]+dp_a[i-1]+dp_l1[i-1]+dp_l2[i-1])%M\n",
    "            dp_l1[i]=(dp_p[i-1]+dp_a[i-1])%M\n",
    "            dp_l2[i]=dp_l1[i-1]\n",
    "            # print('#',i)\n",
    "            # print(dp_p)\n",
    "            # print(dp_l1)\n",
    "            # print(dp_l2)\n",
    "            # print(dp_a)\n",
    "        return (dp_p[-1]+dp_l1[-1]+dp_l2[-1]+dp_a[-1])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        mod = int(1e9) + 7\n",
    "        t = n - 1\n",
    "        m = np.array([[1] * 6,\n",
    "                      [1] + [0] * 5,\n",
    "                      [0, 1] + [0] * 4,\n",
    "                      [0] * 3 + [1] * 3,\n",
    "                      [0] * 3 + [1,0,0],\n",
    "                      [0] * 4 + [1,0]])\n",
    "        m = m.T\n",
    "        r = np.diag([1] * 6)\n",
    "        while t:\n",
    "            if t & 1:\n",
    "                r = np.mod(np.dot(r, m), mod)\n",
    "            t >>= 1\n",
    "            if t:\n",
    "                m = np.mod(np.dot(m, m), mod)\n",
    "        return int(sum(np.mod(np.dot(np.array([1, 0, 0, 1, 1, 0]), r), mod)) % mod)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "#         mod = int(1e9 + 7)\n",
    "#         mp = {}\n",
    "#         # @lru_cache(None)\n",
    "#         def dp(n, a, l):\n",
    "#             if (n, a, l) in mp:\n",
    "#                 return mp[(n, a, l)]\n",
    "#             # base\n",
    "#             if n == 1:\n",
    "#                 if (a == 1 and l == 0) or (a == 0 and l == 1) or (a == 0 and l == 0):\n",
    "\n",
    "#                     return 1\n",
    "#                 else:\n",
    "#                     return 0\n",
    "\n",
    "#             if a == 0 and l == 0:\n",
    "#                 res = (dp(n - 1, 0, 0) + dp(n - 1, 0, 1) + dp(n - 1, 0, 2)) % mod\n",
    "#             elif a == 1 and l == 0:\n",
    "#                 res = (dp(n - 1, 0, 0) + dp(n - 1, 1, 0) + dp(n - 1, 0, 1) + dp(n - 1, 1, 1) + dp(n - 1, 0, 2) + dp(n - 1, 1, 2)) % mod\n",
    "#             elif a == 0 and l == 1:\n",
    "#                 res = dp(n - 1, 0, 0)\n",
    "#             elif a == 1 and l == 1:\n",
    "#                 res = dp(n - 1, 1, 0)\n",
    "#             elif a == 0 and l == 2:\n",
    "#                 res = dp(n - 1, 0, 1)\n",
    "#             elif a == 1 and l == 2:\n",
    "#                 res = dp(n - 1, 1, 1)\n",
    "\n",
    "#             mp[(n, a, l)] = res\n",
    "\n",
    "#             return res\n",
    "        \n",
    "#         return (dp(n, 0, 0) + dp(n, 1, 0) + dp(n, 0, 1) + dp(n, 1, 1) + dp(n, 0, 2)+ dp(n, 1, 2)) % mod\n",
    "\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        dp = [[0] * 6 for _ in range(n + 1)]\n",
    "\n",
    "        dp[1][1] = 1\n",
    "        dp[1][2] = 1\n",
    "        dp[1][0] = 1\n",
    "\n",
    "\n",
    "        for i in range(2, len(dp)):\n",
    "            dp[i][0] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][4]) % mod\n",
    "            dp[i][1] = sum(dp[i - 1]) % mod\n",
    "            dp[i][2] = dp[i - 1][0]\n",
    "            dp[i][3] = dp[i - 1][1]\n",
    "            dp[i][4] = dp[i - 1][2]\n",
    "            dp[i][5] = dp[i - 1][3]\n",
    "\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        dp = [[1, 0, 0] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = sum(dp[i - 1]) % mod\n",
    "            dp[i][1] = dp[i - 1][0]\n",
    "            dp[i][2] = dp[i - 1][1]\n",
    "        dps = [sum(dp[i]) for i in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            res += dps[i] * dps[n - 1 - i]\n",
    "            res %= mod\n",
    "        return (res + dps[n]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        P = [0 for i in range(n)]\n",
    "        \n",
    "        L = [0 for i in range(n)]\n",
    "        LL = [0 for i in range(n)]\n",
    "\n",
    "        A = [0 for i in range(n)]\n",
    "        AP = [0 for i in range(n)]\n",
    "        AL = [0 for i in range(n)]\n",
    "        ALL = [0 for i in range(n)]\n",
    "\n",
    "        P[0], A[0], L[0] = 1, 1, 1\n",
    "        for i in range(1, n):\n",
    "            P[i] = (P[i-1] + L[i-1] + LL[i-1]) % MOD\n",
    "            L[i] = P[i-1]  % MOD\n",
    "            LL[i] = L[i-1]  % MOD\n",
    "\n",
    "            A[i] = P[i]\n",
    "            AP[i] = (A[i-1] + AP[i-1] + AL[i-1] + ALL[i-1]) % MOD\n",
    "            AL[i] = (A[i-1] + AP[i-1]) % MOD\n",
    "            ALL[i] = AL[i-1] % MOD\n",
    "\n",
    "        res = P[-1] + L[-1] + LL[-1] + A[-1] + AP[-1] + AL[-1] + ALL[-1]\n",
    "        res = res % MOD\n",
    "        # print('P', P)\n",
    "        # print('L', L)\n",
    "        # print('LL', LL)\n",
    "        # print('A', A)\n",
    "        # print('AP', AP)\n",
    "        # print('AL', AL)\n",
    "        # print('ALL', ALL)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        A = 0\n",
    "        L = 1\n",
    "        LL = 2\n",
    "        P = 3\n",
    "        AL = 4\n",
    "        ALL = 5\n",
    "        AP = 6\n",
    "\n",
    "        dp = [[0] * 7 for _ in range(n)]\n",
    "        dp[0] = [1,1,0,1,0,0,0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][A] = (dp[i-1][L] + dp[i-1][LL] +dp[i-1][P]) % MOD\n",
    "            dp[i][L] = dp[i-1][P]\n",
    "            dp[i][LL] = dp[i-1][L]\n",
    "            dp[i][P] = (dp[i-1][L] + dp[i-1][LL] + dp[i-1][P]) % MOD\n",
    "\n",
    "            dp[i][AL] = (dp[i-1][A] + dp[i-1][AP]) % MOD\n",
    "            dp[i][ALL] = dp[i-1][AL]\n",
    "            dp[i][AP] = (dp[i-1][A] + dp[i-1][AL] + dp[i-1][ALL] + dp[i-1][AP]) % MOD\n",
    "        \n",
    "        return sum(dp[n-1]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "\n",
    "        ks = 10 ** 9 + 7\n",
    "        dp = [[0 for i in range(5)] for j in range(max(3, n))]\n",
    "        # dp[i][0] 以P为结尾\n",
    "        # dp[i][1] 以A为结尾\n",
    "        # dp[i][2] 以L为结尾\n",
    "        # dp[i][3] 以P为结尾并含有A\n",
    "        # dp[i][4] 以L为结尾并含有A\n",
    "        dp[0] = [1, 1, 1, 0, 0]\n",
    "        dp[1] = [3, 2, 3, 1, 1]\n",
    "        dp[2] = [4, 8, 7, 4, 4]\n",
    "        for i in range(2, n):\n",
    "            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % ks\n",
    "            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2] - dp[i - 1][3] - dp[i - 1][4]) % ks\n",
    "            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][1]) % ks\n",
    "            dp[i][3] = (dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4]) % ks\n",
    "            dp[i][4] = (dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4] - dp[i - 3][3] - dp[i - 3][1]) % ks\n",
    "        return sum(dp[n - 1][:3]) % ks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        dp = [[1, 1, 0, 1, 0, 0] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD\n",
    "            dp[i][1] = (dp[i - 1][0]) % MOD\n",
    "            dp[i][2] = (dp[i - 1][1]) % MOD\n",
    "            dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % MOD\n",
    "            dp[i][4] = (dp[i - 1][3]) % MOD\n",
    "            dp[i][5] = (dp[i - 1][4]) % MOD\n",
    "        return sum(dp[-1]) % MOD\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp = [[0] * 6 for i in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        dp[0][1] = 1\n",
    "        dp[0][2] = 0\n",
    "        dp[0][3] = 0\n",
    "        dp[0][4] = 0\n",
    "        dp[0][5] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]\n",
    "            dp[i][1] = dp[i-1][0] % (10**9+7)\n",
    "            dp[i][2] = dp[i-1][1] % (10**9+7)\n",
    "            dp[i][3] = dp[i-1][5] % (10**9+7)\n",
    "            dp[i][4] = dp[i-1][3] % (10**9+7)\n",
    "            dp[i][5] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5]\n",
    "        return sum(dp[n-1]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # note = {}\n",
    "        MOD = 1e9 + 7\n",
    "        # def dfs(day, absent, late):\n",
    "        #     if day == n:\n",
    "        #         return 1\n",
    "        #     ans = 0\n",
    "        #     if absent < 1:\n",
    "        #         if (day+1, absent+1, late) not in note:\n",
    "        #             note[(day+1, absent+1, 0)] = dfs(day+1, absent+1, 0)\n",
    "        #         ans += note[(day+1, absent+1, 0)]\n",
    "        #         ans %= MOD\n",
    "        #     if late < 2:\n",
    "        #         if (day+1, absent, late+1) not in note:\n",
    "        #             note[(day+1, absent, late+1)] = dfs(day+1, absent, late+1)\n",
    "        #         ans += note[(day+1, absent, late+1)]\n",
    "        #         ans %= MOD\n",
    "        #     if (day+1, absent, 0) not in note:\n",
    "        #         note[(day+1, absent, 0)] = dfs(day+1, absent, 0)\n",
    "        #     ans += note[(day+1, absent, 0)]\n",
    "        #     ans %= MOD\n",
    "        #     return ans % MOD\n",
    "        # return int(dfs(0, 0, 0))\n",
    "        dp = [[[None for _ in range(3)] for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][0][0] = 1\n",
    "        dp[0][0][1] = 1\n",
    "        dp[0][0][2] = 0\n",
    "        dp[0][1][0] = 1\n",
    "        dp[0][1][1] = 0\n",
    "        dp[0][1][2] = 0 \n",
    "        for i in range(1, n):\n",
    "            dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % MOD\n",
    "            dp[i][0][1] = dp[i-1][0][0]\n",
    "            dp[i][0][2] = dp[i-1][0][1]\n",
    "            dp[i][1][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]) % MOD\n",
    "            dp[i][1][1] = dp[i-1][1][0]\n",
    "            dp[i][1][2] = dp[i-1][1][1]\n",
    "        ans = 0\n",
    "        for i in range(2):\n",
    "            for j in range(3):\n",
    "                ans += dp[n-1][i][j]\n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = pow(10, 9) + 7\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # dp\n",
    "        # 1. 缺勤天数\n",
    "        # 2. 连续迟到天数\n",
    "        dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(n + 1)]\n",
    "        dp[0][0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]  # 必须是A\n",
    "            dp[i][0][1] = dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1]  # A\n",
    "            dp[i][0][1]+= dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]  # P\n",
    "            dp[i][0][0] %= MOD\n",
    "            dp[i][0][1] %= MOD\n",
    "            dp[i][1] = dp[i-1][0]  # 必须是L\n",
    "            dp[i][2] = dp[i-1][1]  # 必须是L\n",
    "            # print(dp[i])\n",
    "        return (sum(dp[-1][0]) + sum(dp[-1][1]) + sum(dp[-1][2])) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp = [[[0]*2 for _ in range(3)] for _ in range(n+1)]\n",
    "        dp[1][0][0] = 1\n",
    "        dp[1][1][0] = 1\n",
    "        dp[1][0][1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]) % 1000000007\n",
    "            dp[i][1][0] = dp[i-1][0][0]\n",
    "            dp[i][2][0] = dp[i-1][1][0]\n",
    "            dp[i][0][1] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0] + \\\n",
    "                            dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1]) % 1000000007\n",
    "            dp[i][1][1] = dp[i-1][0][1]\n",
    "            dp[i][2][1] = dp[i-1][1][1]\n",
    "        \n",
    "        return (dp[n][0][0] + dp[n][1][0] + dp[n][2][0] + \\\n",
    "                            dp[n][0][1] + dp[n][1][1] + dp[n][2][1]) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # dp = [[0,0,0], [1,1,1], [2,3,3]]\n",
    "        # for i in range(2, n):\n",
    "        #     dp_new = [0,0,0]\n",
    "        #     dp_new[2] = sum(dp[-1])\n",
    "        #     dp_new[1] = (dp[-2][0] + dp[-2][2]) * 3\n",
    "        #     dp_new[0] = 0\n",
    "            \n",
    "        #     dp.append(dp_new)\n",
    "        #     print(dp)\n",
    "\n",
    "        dp = [[[1,1,0],[1,0,0]]]\n",
    "        for i in range(1, n):\n",
    "            dp_new_0 = [0,0,0]\n",
    "            dp_new_1 = [0,0,0]\n",
    "\n",
    "            dp_new_0[0] = sum(dp[-1][0]) % 1000000007\n",
    "            dp_new_0[1] = dp[-1][0][0]\n",
    "            dp_new_0[2] = dp[-1][0][1]\n",
    "\n",
    "            dp_new_1[0] = dp_new_0[0] + sum(dp[-1][1]) % 1000000007\n",
    "            dp_new_1[1] = dp[-1][1][0] % 1000000007\n",
    "            dp_new_1[2] = dp[-1][1][1]\n",
    "\n",
    "            dp.append([dp_new_0, dp_new_1])\n",
    "            # print(dp)\n",
    "        \n",
    "        return (sum(dp[-1][0]) + sum(dp[-1][1])) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        # 长度，A 的数量，结尾连续 L 的数量\n",
    "        dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n + 1)]\n",
    "        dp[0][0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            # 以 P 结尾的数量\n",
    "            for j in range(0, 2):\n",
    "                for k in range(0, 3):\n",
    "                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD\n",
    "            \n",
    "            # 以 A 结尾的数量\n",
    "            for k in range(0, 3):\n",
    "                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD\n",
    "            \n",
    "            # 以 L 结尾的数量\n",
    "            for j in range(0, 2):\n",
    "                for k in range(1, 3):\n",
    "                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD\n",
    "        \n",
    "        total = 0\n",
    "        for j in range(0, 2):\n",
    "            for k in range(0, 3):\n",
    "                total += dp[n][j][k]\n",
    "        \n",
    "        return total % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        f = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]\n",
    "        f[0][0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(2):\n",
    "                for k in range(3):\n",
    "                    f[i][j][0] = (f[i][j][0] + f[i - 1][j][k]) % MOD\n",
    "                    # f[i][j][0] %= MOD\n",
    "            for k in range(3):\n",
    "                f[i][1][0] = (f[i][1][0] + f[i - 1][0][k]) % MOD\n",
    "                # f[i][1][0] %= MOD\n",
    "            for j in range(2):\n",
    "                for k in range(1, 3):\n",
    "                    f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % MOD\n",
    "                    # f[i][j][k] %= MOD\n",
    "        res = 0\n",
    "        for j in range(2):\n",
    "            for k in range(3):\n",
    "                res += f[n][j][k]\n",
    "                res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp = [[[0, 0, 0] for _ in range(2)] for _ in range(n)]\n",
    "\n",
    "        dp[0][0][0] = 1\n",
    "        dp[0][0][1] = 1\n",
    "        dp[0][0][2] = 1\n",
    "        mod_val = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            dp[i][0][0] = (dp[i - 1][0][1] + dp[i - 1][0][2]) % mod_val\n",
    "            dp[i][1][0] = 0\n",
    "            if i <= 1:\n",
    "                dp[i][0][1] = (dp[i - 1][0][1] + dp[i - 1][0][2]) % mod_val\n",
    "                dp[i][1][1] = (dp[i - 1][0][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % mod_val\n",
    "            else:\n",
    "                dp[i][0][1] = (dp[i - 1][0][2] + dp[i - 2][0][2]) % mod_val\n",
    "                dp[i][1][1] = (dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 2][0][0] + dp[i - 2][1][2]) % mod_val\n",
    "            dp[i][0][2] = (dp[i - 1][0][1] + dp[i - 1][0][2]) % mod_val\n",
    "            dp[i][1][2] = (dp[i - 1][0][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % mod_val\n",
    "        res = 0\n",
    "\n",
    "        last_dp = dp[-1]\n",
    "        for i in range(2):\n",
    "            res += sum(last_dp[i]) % mod_val\n",
    "\n",
    "        return res % mod_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        modnum = 10**9+7\n",
    "        dp = [[[0, 0], [0, 0], [0, 0]]for _ in range(n+1)]\n",
    "        dp[0][0][0] = 1\n",
    "        # 前i天，有连续j天L，有k次A的情况数\n",
    "        for i in range(n):\n",
    "            # A\n",
    "            for j in range(3):\n",
    "                dp[i+1][0][1] = (dp[i+1][0][1] + dp[i][j][0]) % modnum\n",
    "            # L\n",
    "            for j in range(2):\n",
    "                for k in range(2):\n",
    "                    dp[i+1][j+1][k] = (dp[i+1][j+1][k] + dp[i][j][k])\n",
    "            # P\n",
    "            for j in range(3):\n",
    "                for k in range(2):\n",
    "                    dp[i+1][0][k] = (dp[i+1][0][k] + dp[i][j][k]) % modnum\n",
    "        ans = 0\n",
    "        for j in range(3):\n",
    "            for k in range(2):\n",
    "                ans = (ans + dp[n][j][k]) % modnum\n",
    "        return ans      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n + 1)]\n",
    "        dp[0][0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(2):\n",
    "                for k in range(3):\n",
    "                    dp[i][j][0] += dp[i - 1][j][k] % MOD\n",
    "                    if k >= 1:\n",
    "                        dp[i][j][k] += dp[i - 1][j][k - 1] % MOD\n",
    "            for k in range(3):\n",
    "                dp[i][1][0] += dp[i - 1][0][k] % MOD\n",
    "        return (sum(dp[-1][0]) + sum(dp[-1][1])) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        dp = [[[0] * 4 for i in range(3)] for j in range(n + 1)]\n",
    "\n",
    "        for a in [1, 0]:\n",
    "            for lt in [2, 1, 0]:\n",
    "                dp[n][a][lt] = 1\n",
    "\n",
    "\n",
    "        for idx in range(n - 1, -1, -1):\n",
    "            for a in [1, 0]:\n",
    "                for lt in [2, 1, 0]:\n",
    "                    ret = 0\n",
    "                    ret += dp[idx + 1][a][0]\n",
    "                    ret %= MOD\n",
    "\n",
    "                    ret += dp[idx + 1][a + 1][0]\n",
    "                    ret %= MOD\n",
    "\n",
    "                    ret += dp[idx + 1][a][lt + 1]\n",
    "                    ret %= MOD\n",
    "                    dp[idx][a][lt] = ret\n",
    "\n",
    "        return dp[0][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 3\n",
    "        dp = [[[0, 0], [0, 0, 0, 0], [0]] for _ in range(n)]\n",
    "        dp[0][0][0] = 1\n",
    "        dp[0][1][0] = 1\n",
    "        dp[0][2][0] = 1\n",
    "        mod = 1000000007\n",
    "        for i in range(1, n):\n",
    "            dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][1][2]) % mod\n",
    "            dp[i][0][1] = (dp[i-1][0][1] + dp[i-1][1][3] + dp[i-1][1][1] + dp[i-1][2][0]) % mod\n",
    "            dp[i][1][0] = (dp[i-1][0][0]) % mod\n",
    "            dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][2][0]) % mod\n",
    "            dp[i][1][2] = (dp[i-1][1][0]) % mod\n",
    "            dp[i][1][3] = (dp[i-1][1][1]) % mod\n",
    "            dp[i][2][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][1][2]) % mod\n",
    "    \n",
    "        return (sum(dp[-1][0]) + dp[-1][2][0] + sum(dp[-1][1])) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        p_n = 1\n",
    "        a_n = 1\n",
    "        l_n = 1\n",
    "        ll_n = 0\n",
    "        ans_list = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            ans_list[i] = {'p': 0, 'a': 0, 'l': 0, 'll': 0, 'no_a': 0, 'pu': 0, 'lu': 0, 'llu': 0}\n",
    "        # print(ans_list)\n",
    "        ans_list[1]['p'] = 1\n",
    "        ans_list[1]['pu'] = 1\n",
    "        ans_list[1]['a'] = 1\n",
    "        ans_list[1]['l'] = 1\n",
    "        ans_list[1]['lu'] = 1\n",
    "        ans_list[1]['no_a'] = 2\n",
    "        for i in range(1, n):\n",
    "            palll = ans_list[i]['p'] + ans_list[i]['a'] + ans_list[i]['l'] + ans_list[i]['ll']\n",
    "            pu = ans_list[i]['no_a']\n",
    "            l = ans_list[i]['l']\n",
    "            pa = ans_list[i]['p'] + ans_list[i]['a']\n",
    "            lu = ans_list[i]['pu']\n",
    "            llu = ans_list[i]['lu']\n",
    "            no_a = pu + lu + llu\n",
    "            ans_list[i+1]['no_a'] = no_a % mod\n",
    "            ans_list[i+1]['p'] = palll % mod\n",
    "            ans_list[i+1]['a'] = ans_list[i]['no_a'] % mod\n",
    "            ans_list[i+1]['l'] = pa % mod\n",
    "            ans_list[i+1]['ll'] = l % mod\n",
    "            ans_list[i+1]['pu'] = pu % mod\n",
    "            ans_list[i+1]['lu'] = lu % mod\n",
    "            ans_list[i+1]['llu'] = llu % mod\n",
    "        ans = (ans_list[n]['p'] + ans_list[n]['a'] + ans_list[n]['l'] + ans_list[n]['ll']) % mod\n",
    "        # print(ans_list)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        if n == 1: return 3\n",
    "        if n == 2: return 8 \n",
    "        dp, sm, MOD = [1, 1, 2] + [0] * ((n + 1)//2 -2), 0, 1000000007\n",
    "        for i in range (3, (n + 1)//2 + 1):\n",
    "            dp[i] = (dp[i - 3] + dp[i - 2] + dp[i -1] % MOD) \n",
    "        if n % 2 : sm = dp[-1] ** 2\n",
    "        a, b, c = dp[-1] + dp[-2] + dp[-3], dp[-1], dp[-2]\n",
    "        for i in range (n // 2):\n",
    "            sm = (sm + 2 * a * dp[n//2-i] ) % MOD\n",
    "            a, b, c = (a+b+c) % MOD, a, b\n",
    "        return (sm + a) % MOD \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        a = []\n",
    "        for i in range(0, n+1):\n",
    "            a.append([\n",
    "                [0, 0, 0, 0],\n",
    "                [0, 0, 0, 0],\n",
    "                [0, 0, 0, 0],\n",
    "            ])\n",
    "\n",
    "            if i == 0:\n",
    "                a[0][0][0] = 1\n",
    "                continue\n",
    "\n",
    "            a[i][0][0] += a[i-1][0][0]\n",
    "            a[i][0][1] += a[i-1][0][0]\n",
    "            a[i][1][0] += a[i-1][0][0]\n",
    "            a[i][0][0] += a[i-1][0][1]\n",
    "            a[i][0][2] += a[i-1][0][1]\n",
    "            a[i][1][0] += a[i-1][0][1]\n",
    "            a[i][0][0] += a[i-1][0][2]\n",
    "            # a[i][0][3] += a[i-1][0][2]\n",
    "            a[i][1][0] += a[i-1][0][2]\n",
    "            # a[i][0][3] += a[i-1][0][3]\n",
    "            # a[i][0][3] += a[i-1][0][3]\n",
    "            # a[i][1][3] += a[i-1][0][3]\n",
    "\n",
    "            a[i][1][0] += a[i-1][1][0]\n",
    "            a[i][1][1] += a[i-1][1][0]\n",
    "            a[i][2][0] += a[i-1][1][0]\n",
    "            a[i][1][0] += a[i-1][1][1]\n",
    "            a[i][1][2] += a[i-1][1][1]\n",
    "            a[i][2][0] += a[i-1][1][1]\n",
    "            a[i][1][0] += a[i-1][1][2]\n",
    "            # a[i][1][3] += a[i-1][1][2]\n",
    "            a[i][2][0] += a[i-1][1][2]\n",
    "            # a[i][1][3] += a[i-1][1][3]\n",
    "            # a[i][1][3] += a[i-1][1][3]\n",
    "            # a[i][2][3] += a[i-1][1][3]\n",
    "\n",
    "            # a[i][2][0] += a[i-1][2][0]\n",
    "            # a[i][2][1] += a[i-1][2][0]\n",
    "            # a[i][2][0] += a[i-1][2][0]\n",
    "            # a[i][2][0] += a[i-1][2][1]\n",
    "            # a[i][2][2] += a[i-1][2][1]\n",
    "            # a[i][2][0] += a[i-1][2][1]\n",
    "            # a[i][2][0] += a[i-1][2][2]\n",
    "            # a[i][2][3] += a[i-1][2][2]\n",
    "            # a[i][2][0] += a[i-1][2][2]\n",
    "            # a[i][2][3] += a[i-1][2][3]\n",
    "            # a[i][2][3] += a[i-1][2][3]\n",
    "            # a[i][2][3] += a[i-1][2][3]\n",
    "\n",
    "            for j in range(3):\n",
    "                for k in range(4):\n",
    "                    a[i][j][k] %= 10000_00007\n",
    "\n",
    "        return (a[n][0][0] + a[n][0][1] + a[n][0][2] + a[n][1][0] + a[n][1][1] + a[n][1][2]) % 10000_00007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp = [[[0] * 5 for _ in range(4)] for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            for a in range(2, -1, -1):\n",
    "                for l in range(3, -1, -1):\n",
    "                    if a < 2 and l < 3:\n",
    "                        if i == 0:\n",
    "                            dp[i][a][l] = 1\n",
    "                        else:\n",
    "                            dp[i][a][l] = (dp[i - 1][a + 1][0] + dp[i - 1][a][l + 1] + dp[i - 1][a][0]) % 1000000007\n",
    "\n",
    "        return dp[n][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dic_count = {}\n",
    "\n",
    "    def count_n(self, n: int, a: int, l: int):\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        my_str = \"n\" + str(n) + \"a\" + str(a) + \"l\" + str(l)\n",
    "        if self.dic_count.get(my_str) is not None:\n",
    "            return self.dic_count.get(my_str)\n",
    "        if a > 0:\n",
    "            i = self.count_n(n - 1, a - 1, 2)\n",
    "        else:\n",
    "            i = 0\n",
    "        if l > 0:\n",
    "            j = self.count_n(n - 1, a, l - 1)\n",
    "        else:\n",
    "            j = 0\n",
    "        k = self.count_n(n - 1, a, 2)\n",
    "        count = (i + j + k) % (10 ** 9 + 7)\n",
    "        self.dic_count[my_str] = count\n",
    "        return count\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            self.count_n(i + 1, 1, 2)\n",
    "        return self.count_n(n, 1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "\n",
    "        # O(n)\n",
    "        # O(n)\n",
    "\n",
    "        if n == 1: return 3\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        d = [[defaultdict(int) for _ in range(n+1)] for _ in range(2)]\n",
    "        d[1][2][0] += 1\n",
    "        d[1][2][0] += 1\n",
    "        d[1][2][1] += 1\n",
    "        d[1][2][2] += 1\n",
    "        d[0][2][0] += 1\n",
    "        d[0][2][2] += 1\n",
    "        d[0][2][1] += 1\n",
    "        d[0][2][3] += 1\n",
    "\n",
    "        for i in range(2):\n",
    "            for j in range(2, n):\n",
    "                for key, value in d[i][j].items():\n",
    "                    if i == 0:\n",
    "                        d[i+1][j+1][(key%2) << 1] += value % mod\n",
    "                    if key != 3:\n",
    "                        d[i][j+1][((key%2) << 1)+1] += value % mod\n",
    "                    d[i][j+1][(key%2) << 1] += value % mod\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(2):\n",
    "            for value in d[i][-1].values():\n",
    "                res += value % mod\n",
    "        \n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp =[[[0, 0, 0], [0, 0, 0]] for _ in range(n + 1)]\n",
    "        dp[0][0][0] = 1\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(2):\n",
    "                for k in range(3):\n",
    "                    dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][k]) % MOD #当第i天是P；\n",
    "            \n",
    "            #当第i天是A；\n",
    "            for k in range(3):\n",
    "                dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % MOD\n",
    "            \n",
    "            #当第i天是L；\n",
    "            for j in range(2):\n",
    "                for k in range(2):\n",
    "                    dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][j][k]) % MOD\n",
    "        \n",
    "        dp = numpy.array(dp)\n",
    "        return sum(sum(dp[n])).tolist() % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        #A<2 L+L<3\n",
    "        dp = dict()\n",
    "        for x in range(n):\n",
    "            dp[x]={}\n",
    "            for y in range(2):\n",
    "                dp[x][y]={}\n",
    "                for z in range(3):\n",
    "                    dp[x][y][z]=0\n",
    "        dp[0][0][0] = 1\n",
    "        dp[0][1][0] = 1\n",
    "        dp[0][0][1] = 1\n",
    "\n",
    "        for i in range(1,n): \n",
    "            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD\n",
    "            dp[i][1][0] = (dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD\n",
    "            dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD\n",
    "            dp[i][0][1] = dp[i - 1][0][0];\n",
    "            dp[i][0][2] = dp[i - 1][0][1];\n",
    "            dp[i][1][1] = dp[i - 1][1][0];\n",
    "            dp[i][1][2] = dp[i - 1][1][1];\n",
    "        ans = 0;\n",
    "        for i in range(2):\n",
    "            for j in range(3):\n",
    "                ans = (ans + dp[n - 1][i][j]) % MOD\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "mod = 1000000007\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(i: int, a: int, l: int) -> int:\n",
    "    if i == 0: return 1\n",
    "    cnt = 0\n",
    "    if l < 2: cnt += dfs(i - 1, a, l + 1)\n",
    "    if a < 1: cnt += dfs(i - 1, a + 1, 0)\n",
    "    cnt += dfs(i - 1, a, 0)\n",
    "    return cnt % mod\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dfs(i, 0, 0)\n",
    "\n",
    "        return dfs(n, 0, 0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return 3\n",
    "\n",
    "        dp = {}\n",
    "        # 7 sub state...\n",
    "        dp[(1, 0)] = 1  # 0A 0L\n",
    "        dp[(1, 1)] = 1  # 1A 0L\n",
    "        dp[(1, 2)] = 1  # 0A 1L\n",
    "        dp[(1, 3)] = 0  # 0A 2L\n",
    "        dp[(1, 4)] = 0  # 1A 1L\n",
    "        dp[(1, 5)] = 0  # 1A 2L\n",
    "        cnt = 0\n",
    "        for i in range(2, n + 1):\n",
    "            # add p?\n",
    "            dp[(i, 0)] = 0\n",
    "            dp[(i, 1)] = 0\n",
    "            dp[(i, 2)] = 0\n",
    "            dp[(i, 3)] = 0\n",
    "            dp[(i, 4)] = 0\n",
    "            dp[(i, 5)] = 0\n",
    "\n",
    "            dp[(i, 0)] += dp[(i - 1, 0)] + dp[(i - 1, 2)] + dp[(i - 1, 3)]\n",
    "            dp[(i, 1)] += dp[(i - 1, 0)] + dp[(i - 1, 2)] + dp[(i - 1, 3)] + dp[(i - 1, 1)] + dp[(i - 1, 4)] + dp[(i - 1, 5)]\n",
    "            dp[(i, 2)] += dp[(i - 1, 0)]\n",
    "            dp[(i, 3)] += dp[(i - 1, 2)]\n",
    "            dp[(i, 4)] += dp[(i - 1, 1)]\n",
    "            dp[(i, 5)] += dp[(i - 1, 4)]\n",
    "\n",
    "            dp[(i, 0)] %= (10 ** 9 + 7)\n",
    "            dp[(i, 1)] %= (10 ** 9 + 7)\n",
    "            dp[(i, 2)] %= (10 ** 9 + 7)\n",
    "            dp[(i, 3)] %= (10 ** 9 + 7)\n",
    "            dp[(i, 4)] %= (10 ** 9 + 7)\n",
    "            dp[(i, 5)] %= (10 ** 9 + 7)\n",
    "\n",
    "        for i in range(6):\n",
    "            cnt += dp[(n, i)]\n",
    "            cnt %= 10 ** 9 + 7\n",
    "        return cnt % (10 ** 9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[[[0]*3 for _ in range(3)] for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][1][0][0] = dp[0][0][1][1] = dp[0][0][0][2] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][1][0][0] = (dp[i-1][0][0][2]+dp[i-1][0][1][1]+dp[i-1][0][2][1])%mod\n",
    "            for m in range(1, 3):\n",
    "                for k in range(2):\n",
    "                    if m == 1:\n",
    "                        dp[i][k][m][1] = ((dp[i-1][k][0][0] if k > 0 else 0)+dp[i-1][k][0][2])%mod\n",
    "                    else:\n",
    "                        dp[i][k][m][1] = dp[i-1][k][m-1][1]\n",
    "            for k in range(2):\n",
    "                dp[i][k][0][2] = (dp[i-1][k][0][2]+dp[i-1][k][1][1]+dp[i-1][k][2][1]+(dp[i-1][k][0][0] if k > 0 else 0))%mod\n",
    "        res = 0\n",
    "        for k in range(2):\n",
    "            for m in range(3):\n",
    "                for j in range(3):\n",
    "                    res = (res+dp[-1][k][m][j])%mod\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        p=10**9 + 7\n",
    "        from collections import defaultdict\n",
    "        def f1():\n",
    "            return defaultdict(int)\n",
    "        def f2():\n",
    "            return defaultdict(f1)\n",
    "        dp=defaultdict(f2)\n",
    "\n",
    "        dp[0][0][0]=1\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%p\n",
    "            dp[i][0][1]=dp[i-1][0][0]%p\n",
    "            dp[i][0][2]=dp[i-1][0][1]%p\n",
    "            dp[i][1][0]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]+dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2])%p\n",
    "            dp[i][1][1]=dp[i-1][1][0]%p\n",
    "            dp[i][1][2]=dp[i-1][1][1]%p\n",
    "        return (dp[n][0][0]+dp[n][0][1]+dp[n][0][2]+dp[n][1][0]+dp[n][1][1]+dp[n][1][2])%p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    NMAX = 10**9+7\n",
    "\n",
    "    @classmethod\n",
    "    def passDict(self, n:int) -> dict:\n",
    "        if n == 1:\n",
    "            return {'AL2':0, 'AL1':0, 'AL0':1, 'L2':0, 'L1':1, 'L0':1}\n",
    "        else:\n",
    "            dict0 = Solution().passDict(n-1)\n",
    "            return {'AL2':(dict0['AL1']) % Solution.NMAX,\n",
    "                    'AL1': (dict0['AL0']) % Solution.NMAX,\n",
    "                    'AL0': (dict0['AL2'] + dict0['AL1'] + dict0['AL0'] + dict0['L2'] + dict0['L1'] + dict0['L0']) % Solution.NMAX,\n",
    "                    'L2': (dict0['L1']) % Solution.NMAX,\n",
    "                    'L1': (dict0['L0']) % Solution.NMAX,\n",
    "                    'L0': (dict0['L2'] + dict0['L1'] + dict0['L0']) % Solution.NMAX}\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dictN = Solution().passDict(n)\n",
    "        return sum(dictN.values()) % Solution.NMAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    NMAX = 10**9+7\n",
    "\n",
    "    @classmethod\n",
    "    def passDict(self, n:int) -> dict:\n",
    "        if n == 2:\n",
    "            return {'0PP':1, '0PL':1, '0LP':1, '0LL':1,\n",
    "                    '1AP':1, '1PA':1, '1AL':1, '1LA':1,\n",
    "                    '1PP':0, '1PL':0, '1LP':0, '1LL':0}\n",
    "\n",
    "        elif n > 2:\n",
    "            dict0 = Solution().passDict(n-1)\n",
    "            return {'0PP':(dict0['0PP'] + dict0['0LP']) % Solution.NMAX,\n",
    "                    '0PL':(dict0['0PP'] + dict0['0LP']) % Solution.NMAX,\n",
    "                    '0LP':(dict0['0LL'] + dict0['0PL']) % Solution.NMAX,\n",
    "                    '0LL':dict0['0PL'] % Solution.NMAX,\n",
    "                    '1AP':(dict0['1PA'] + dict0['1LA']) % Solution.NMAX,\n",
    "                    '1AL':(dict0['1PA'] + dict0['1LA']) % Solution.NMAX,\n",
    "                    '1PA':(dict0['0PP'] + dict0['0LP']) % Solution.NMAX,\n",
    "                    '1LA':(dict0['0LL'] + dict0['0PL']) % Solution.NMAX,\n",
    "                    '1PP':(dict0['1PP'] + dict0['1LP'] + dict0['1AP']) % Solution.NMAX,\n",
    "                    '1PL':(dict0['1PP'] + dict0['1LP'] + dict0['1AP']) % Solution.NMAX,\n",
    "                    '1LP':(dict0['1LL'] + dict0['1PL'] + dict0['1AL']) % Solution.NMAX,\n",
    "                    '1LL':(dict0['1PL'] + dict0['1AL']) % Solution.NMAX}\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 3\n",
    "        elif n == 2:\n",
    "            return 8\n",
    "        else:\n",
    "            dictN = Solution().passDict(n)\n",
    "            return sum(dictN.values()) % Solution.NMAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MASK = 1000000007\n",
    "\n",
    "\n",
    "# dp[length][flag] = count\n",
    "# flag: ind[0-5] => {A0L0,A0L1,A0L2,A1L0,A1L1,A1L2}\n",
    "# Ln stand for trailing n Ls\n",
    "@functools.lru_cache()\n",
    "def dp(i: int):\n",
    "    if i == 1:\n",
    "        # A:A1L0, L:A0L1, P:A0L0\n",
    "        return 1, 1, 0, 1, 0, 0\n",
    "\n",
    "    A0L0, A0L1, A0L2, A1L0, A1L1, A1L2 = dp(i-1)\n",
    "    # A0L0 -> A:A1L0, L:A0L1, P:A0L0\n",
    "    # A0L1 -> A:A1L0, L:A0L2, P:A0L0\n",
    "    # A0L2 -> A:A1L0, L:XXXX, P:A0L0\n",
    "    # A1L0 -> A:XXXX, L:A1L1, P:A1L0\n",
    "    # A1L1 -> A:XXXX, L:A1L2, P:A1L0\n",
    "    # A1L2 -> A:XXXX, L:XXXX, P:A1L0\n",
    "    return (A0L0 + A0L1 + A0L2) % MASK,\\\n",
    "           A0L0,\\\n",
    "           A0L1,\\\n",
    "           (A0L0 + A0L1 + A0L2 + A1L0 + A1L1 + A1L2) % MASK,\\\n",
    "           A1L0,\\\n",
    "           A1L1\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        return sum(dp(n)) %  MASK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        return self.dfs(0,n,0,0)\n",
    "    @lru_cache\n",
    "    def dfs(self,days,n,ab,late):\n",
    "        if days >= n :\n",
    "            return 1\n",
    "        ans = 0\n",
    "        ans = (ans + self.dfs(days+1,n,ab,0)) % (10**9 + 7)\n",
    "        if ab < 1:\n",
    "            ans = (ans + self.dfs(days+1,n,1,0)) % (10**9 + 7)\n",
    "        if late < 2:\n",
    "            ans = (ans + self.dfs(days+1,n,ab,late+1)) % (10**9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def func1(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    if n == 1:\n",
    "        return 2\n",
    "    if n == 2:\n",
    "        return 4\n",
    "    n2 = func1(n - 1)\n",
    "    n3 = func1(n - 2)\n",
    "    n4 = func1(n - 3)\n",
    "    return (n2 + n3 + n4) % (1000000007)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n):\n",
    "        if n == 1:\n",
    "            return 3\n",
    "        n1 = func1(n)\n",
    "        n1 += func1(n - 1) * 2\n",
    "        for i in range(1, n - 1):\n",
    "            n1 += func1(i) * func1(n - 1 - i)\n",
    "        return n1 % (1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = 1000000007\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        memo = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n)]\n",
    "        # print(memo)\n",
    "        return self.dfs(0, n, 0, 0, memo)\n",
    "\n",
    "    def dfs(self, day, n, absent, late, memo):\n",
    "        if day >= n:\n",
    "            return 1\n",
    "        if memo[day][absent][late] != 0:\n",
    "            return memo[day][absent][late]\n",
    "        ans = 0\n",
    "        ans = (ans + self.dfs(day + 1, n, absent, 0, memo)) % self.MOD\n",
    "        if absent < 1:\n",
    "            ans = (ans + self.dfs(day + 1, n, 1, 0, memo)) % self.MOD\n",
    "        if late < 2:\n",
    "            ans = (ans + self.dfs(day + 1, n, absent, late + 1, memo)) % self.MOD\n",
    "        memo[day][absent][late] = ans\n",
    "\n",
    "        return ans\n",
    "\n",
    "# so = Solution()\n",
    "# print(so.checkRecord(1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        def dp(n, A, L):\n",
    "            if n == 0: return 1\n",
    "            if mp[n][A][L] != -1: return mp[n][A][L]\n",
    "            ans = dp(n-1, A, 0)\n",
    "            if A < 1: ans += dp(n-1, A+1, 0)\n",
    "            if L < 2: ans += dp(n-1, A, L+1)\n",
    "            mp[n][A][L] = ans%(10**9+7)\n",
    "            return mp[n][A][L]\n",
    "        \n",
    "        mp = [[[-1]*4 for _ in range(2)] for _ in range(n+1)]\n",
    "        return dp(n, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def checkRecord(self, n: int) -> int:\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * 3 for _ in range(2)] for _ in range(n+1)]\n",
    "#         dp[0][0][0] = 1\n",
    "#         for i in range(1, n+1):\n",
    "#             dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % MOD\n",
    "#             dp[i][0][1] = dp[i-1][0][0]\n",
    "#             dp[i][0][2] = dp[i-1][0][1]\n",
    "#             dp[i][1][0] = (dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % MOD\n",
    "#             dp[i][1][1] = dp[i-1][1][0]\n",
    "#             dp[i][1][2] = dp[i-1][1][1]\n",
    "#         return (sum(dp[-1][0]) + sum(dp[-1][1])) % MOD\n",
    "\n",
    "\n",
    "# ! 另一种状态机DP写法同样也是记忆化搜索（这个状态理解以后写起来更轻松）\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        @functools.lru_cache()\n",
    "        def dfs(n, acnt, lcnt):\n",
    "            if n == 0: # ! 从上往下因为不想多传一个参数\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            cnt += dfs(n-1, acnt, 0) # P\n",
    "            if lcnt < 2: cnt += dfs(n-1, acnt, lcnt+1) # L\n",
    "            if acnt == 0: cnt += dfs(n-1, 1, 0) # A\n",
    "            return cnt % (10**9+7)\n",
    "        return dfs(n, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def checkRecord(self, n: int) -> int:\n",
    "    #     # dp = [[[0, 0, 0] for _ in range(2)] for _ in range(n)]\n",
    "\n",
    "    #     \"\"\"\n",
    "    #     dp[i][j][k] represents in day i with j times of absence and k times of late.\n",
    "    #     \"\"\"\n",
    "\n",
    "    #     def dp(i: int, j: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             if j == 0 and k == 2:\n",
    "    #                 return 0\n",
    "    #             if j == 1 and k > 0:\n",
    "    #                 return 0\n",
    "    #             return 1\n",
    "    #         a00 = dp(i - 1, 0, 0) + dp(i - 1, 0, 1) + dp(i - 1, 0, 2)\n",
    "    #         a01 = dp(i - 1, 0, 0)\n",
    "    #         a02 = dp(i - 1, 0, 1)\n",
    "    #         a10 = (\n",
    "    #             dp(i - 1, 1, 0)\n",
    "    #             + dp(i - 1, 1, 1)\n",
    "    #             + dp(i - 1, 1, 2)\n",
    "    #             + dp(i - 1, 0, 0)\n",
    "    #             + dp(i - 1, 0, 1)\n",
    "    #             + dp(i - 1, 0, 2)\n",
    "    #         )\n",
    "    #         a11 = dp(i - 1, 1, 0)\n",
    "    #         a12 = dp(i - 1, 1, 1)\n",
    "\n",
    "    #         return (a00 + a01 + a02 + a10 + a11 + a12) % MOD\n",
    "\n",
    "    #     MOD = 10**9 + 7\n",
    "    #     return dp(n, 1, 2)\n",
    "\n",
    "    # def checkRecord(self, n: int) -> int:\n",
    "    #     dp = [[[0, 0, 0] for _ in range(2)] for _ in range(n)]\n",
    "\n",
    "    #     dp[0][0][0] = 1\n",
    "    #     dp[0][0][1] = 1\n",
    "    #     dp[0][1][0] = 1\n",
    "\n",
    "    #     MOD = 10**9 + 7\n",
    "\n",
    "    #     for i in range(1, n):\n",
    "    #         dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD\n",
    "    #         dp[i][0][1] = dp[i - 1][0][0]\n",
    "    #         dp[i][0][2] = dp[i - 1][0][1]\n",
    "    #         dp[i][1][0] = (\n",
    "    #             dp[i - 1][0][0]\n",
    "    #             + dp[i - 1][0][1]\n",
    "    #             + dp[i - 1][0][2]\n",
    "    #             + dp[i - 1][1][0]\n",
    "    #             + dp[i - 1][1][1]\n",
    "    #             + dp[i - 1][1][2]\n",
    "    #         ) % MOD\n",
    "\n",
    "    #         dp[i][1][1] = dp[i - 1][1][0]\n",
    "    #         dp[i][1][2] = dp[i - 1][1][1]\n",
    "\n",
    "    #     summ = 0\n",
    "    #     for i in range(2):\n",
    "    #         for j in range(3):\n",
    "    #             summ += dp[n - 1][i][j]\n",
    "\n",
    "    #     return summ % MOD\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # 1.DFS\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(day: int, absent: int, late: int) -> int:\n",
    "            if day == n:\n",
    "                return 1\n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            # 1.put present\n",
    "            ans = (ans + dfs(day + 1, absent, 0)) % MOD\n",
    "\n",
    "            # 2.put absent\n",
    "            if absent == 0:\n",
    "                ans = (ans + dfs(day + 1, 1, 0)) % MOD\n",
    "\n",
    "            # 3.put late\n",
    "            if late < 2:\n",
    "                ans = (ans + dfs(day + 1, absent, late + 1)) % MOD\n",
    "\n",
    "            return ans\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        return dfs(0, 0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @functools.lru_cache()\n",
    "        def dfs(day, n, absent, late) :\n",
    "            if (day >= n) :\n",
    "                return 1          \n",
    "            ans = dfs(day + 1, n, absent, 0) # 1. Present随便放        \n",
    "            if (absent < 1) :                # 2. Absent最多只能放一个\n",
    "                ans += dfs(day + 1, n, 1, 0)                \n",
    "            if (late < 2) :                  # 3. Late最多连续放2个\n",
    "                ans += dfs(day + 1, n, absent, late + 1)      \n",
    "            return ans % MOD\n",
    "        return dfs(0, n, 0, 0)\n",
    "        @cache\n",
    "        def dfs(cnt=0,l=0,a=0):\n",
    "            if cnt == n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            if l < 2:\n",
    "                ans += dfs(cnt+1,l+1,a)\n",
    "            if a < 1:\n",
    "                ans += dfs(cnt+1,0,a+1)\n",
    "            ans += dfs(cnt+1,0,a)\n",
    "            return ans%(10**9+7)\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp=[[[-1]*3 for i in range(2)]for j in range(n+1)]\n",
    "        mod=10**9+7\n",
    "     \n",
    "        def dfs(a,l,res):\n",
    "            if res==0:\n",
    "                return 1\n",
    "            elif dp[res][a][l]!=-1:\n",
    "                return dp[res][a][l]\n",
    "            t=0\n",
    "            if l<=1:\n",
    "                t=(t+dfs(a,l+1,res-1))%mod\n",
    "            if a==0:\n",
    "                t=(t+dfs(a+1,0,res-1))%mod\n",
    "            t=(t+dfs(a,0,res-1))%mod\n",
    "            dp[res][a][l]=t\n",
    "            return t\n",
    "        return dfs(0,0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # @lru_cache(None)\n",
    "        memo = [[[None]*3 for __ in range(2)] for _ in range(n)]\n",
    "        def dfs(i, absent, late):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if memo[i][absent][late] != None:\n",
    "                return memo[i][absent][late]\n",
    "            ans = 0\n",
    "            ans += dfs(i+1, absent, 0)\n",
    "            if absent < 1:\n",
    "                ans += dfs(i+1, absent+1, 0)\n",
    "            if late < 2:\n",
    "                ans += dfs(i+1, absent, late+1)\n",
    "            memo[i][absent][late] = ans % 1000000007\n",
    "            return memo[i][absent][late]\n",
    "        \n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(cur_day, cur_L, cur_A):\n",
    "            nonlocal n, mod\n",
    "            if cur_day >= n:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "\n",
    "            # put \"P\"\n",
    "            res = (res + dfs(cur_day+1, 0, cur_A)) % mod\n",
    "            # put \"A\"\n",
    "            if cur_A < 1:\n",
    "                res = (res + dfs(cur_day+1, 0, cur_A+1)) % mod\n",
    "            # put L\n",
    "            if cur_L < 2:\n",
    "                res = (res + dfs(cur_day+1, cur_L+1, cur_A)) % mod\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # A < 2 \n",
    "        # L < 3 consecutive days \n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def search(ab, late, length, cache):\n",
    "            if length == n:\n",
    "                return 1\n",
    "            \n",
    "            if cache[length][ab][late] is None:\n",
    "                sums = 0\n",
    "                if ab < 1:\n",
    "                    sums = (sums + search(ab + 1, 0, length + 1, cache)) % MOD\n",
    "                if late < 2:\n",
    "                    sums = (sums + search(ab, late + 1, length + 1, cache)) % MOD\n",
    "                \n",
    "                cache[length][ab][late] = (sums + search(ab, 0, length + 1, cache)) % MOD \n",
    "\n",
    "            return cache[length][ab][late]\n",
    "\n",
    "\n",
    "        return search(0, 0, 0, [[[None] * 3 for j in range(2)] for i in range(n + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "        self.mod = 1e9 + 7\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # 把 对应的 字符转化为 数字状态进行存储，利用 数字 判别   *** 技巧 ******\n",
    "        # 进行搜索时 利用记忆化搜索判定重复项\n",
    "\n",
    "        def dfs(day, n, absent, lates, vis):\n",
    "            if day >= n:\n",
    "                return 1\n",
    "            # 相同的状态需要剔除\n",
    "            if vis[day][absent][lates] != 0:\n",
    "                return vis[day][absent][lates]\n",
    "            ans = self.ans\n",
    "            # 注意： 由于L需要 连续，故填充其他 字符时，lates 直接置为 0\n",
    "            # Present 随便放\n",
    "            ans = (ans + dfs(day + 1, n, absent, 0, vis)) % self.mod\n",
    "            # Absent 最多放一个\n",
    "            if absent < 1:\n",
    "                ans = (ans + dfs(day + 1, n, 1, 0, vis)) % self.mod\n",
    "            # late 最多连续放两个\n",
    "            if lates < 2:\n",
    "                ans = (ans + dfs(day + 1, n, absent, lates + 1, vis)) % self.mod\n",
    "            vis[day][absent][lates] = ans\n",
    "            return ans \n",
    "        vis = [[[0]*(3) for _ in range(2)] for _ in range(n)]\n",
    "        return int(dfs(0, n, 0, 0, vis))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        dp=[[[-1]*3 for i in range(2)]for j in range(n+1)]\n",
    "        mod=10**9+7\n",
    "     \n",
    "        def dfs(a,l,res):\n",
    "            if res==0:\n",
    "                return 1\n",
    "            elif dp[res][a][l]!=-1:\n",
    "                return dp[res][a][l]\n",
    "            t=0\n",
    "            if l<=1:\n",
    "                t=(t+dfs(a,l+1,res-1))%mod\n",
    "            if a==0:\n",
    "                t=(t+dfs(a+1,0,res-1))%mod\n",
    "            t=(t+dfs(a,0,res-1))%mod\n",
    "            dp[res][a][l]=t\n",
    "            return t\n",
    "        return dfs(0,0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        cache = [[[-1 for k in range(3)] for j in range(2)] for i in range(n+1)]\n",
    "\n",
    "        def dfs(n, acnt, lcnt):            \n",
    "            if n == 0: return 1\n",
    "\n",
    "            if cache[n][acnt][lcnt] != -1: return cache[n][acnt][lcnt]\n",
    "\n",
    "            ans = 0\n",
    "            if acnt < 1:\n",
    "                ans = dfs(n-1, acnt+1, 0) % MOD\n",
    "            if lcnt < 2:\n",
    "                ans = (ans + dfs(n-1, acnt, lcnt+1)) % MOD\n",
    "            ans = (ans + dfs(n-1, acnt, 0)) % MOD\n",
    "            cache[n][acnt][lcnt] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(n, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        e = 10**9+7\n",
    "        # _,_,_A,_,_\n",
    "        \"\"\"\n",
    "        1. 1个A ==>f(x,1)= sum(f(x1,0)*f(x-1-x1,0))\n",
    "        2. 0个A ==>f(x,0)=f(x-1,0) + f(x-2,0)+(x-3,0)\n",
    "        \n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def f(x,t):\n",
    "            if t==0:\n",
    "                if x==0:\n",
    "                    return 1\n",
    "                if x < 3:\n",
    "                    return 2*x\n",
    "                return (f(x-1,0)+f(x-2,0)+f(x-3,0))%e \n",
    "            else:\n",
    "                if x< 2:\n",
    "                    return 1\n",
    "                if x%2==0:\n",
    "                    return 2*sum([f(k,0)*f(x-1-k,0) for k in range(x//2)])%e \n",
    "                return (2*sum([f(k,0)*f(x-1-k,0) for k in range(x//2)])+f(x//2,0)**2)%e \n",
    "        return (f(n,0)+f(n,1))%e "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        # 长度为n、总共a天缺勤、最近连续l天迟到的获奖出勤记录有多少种\n",
    "        # 返回值对应的(a, l)取值为[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]\n",
    "        @lru_cache(None)\n",
    "        def dp(n: int):\n",
    "            if n == 0:\n",
    "                return [1] + [0] * 5\n",
    "            a, b, c, d, e, f = dp(n - 1)\n",
    "            return [i % Solution.mod for i in [a + b + c, a, b, a + b + c + d + e + f, d, e]]\n",
    "\n",
    "        return sum(dp(n)) % Solution.mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "@lru_cache(None)\n",
    "def dfs(n, a, l):\n",
    "    if n == 0: return 1\n",
    "    res = dfs(n - 1, a, 0)\n",
    "    if a == 0: res += dfs(n - 1, 1, 0)\n",
    "    if l < 2: res += dfs(n - 1, a, l + 1)\n",
    "    return res % mod\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        return dfs(n, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def f(n, a, l):\n",
    "    if n == 0: return 1\n",
    "    rnt = f(n-1, a, 0)\n",
    "    if a < 1: rnt += f(n-1, a+1, 0)\n",
    "    if l < 2: rnt += f(n-1, a, l+1)\n",
    "    return rnt % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        return f(n, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        memo = [[[0,0,0],[0,0,0]] for _ in range(n+1)]\n",
    "        MOD = 10**9 + 7\n",
    "        def dfs(A,L,P,cur):\n",
    "            if cur == n:\n",
    "                return 1\n",
    "            if memo[cur][A][L]!=0:return memo[cur][A][L]\n",
    "            ans = 0\n",
    "            if A<1:\n",
    "                ans = (ans + dfs(A+1,0,P,cur+1))%MOD\n",
    "            if L<2:\n",
    "                ans = (ans + dfs(A,L+1,P,cur+1))%MOD\n",
    "            ans = (ans + dfs(A,0,P+1,cur+1))%MOD\n",
    "            memo[cur][A][L] = ans\n",
    "            return ans\n",
    "        ans = dfs(0,0,0,0)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        memo = [[[0]*3 for i in range(2)] for i in range(n)]\n",
    "        MOD = 1e9+7\n",
    "        @lru_cache\n",
    "        def dfs(day,absent,late):\n",
    "            if day >= n:\n",
    "                return 1\n",
    "            if memo[day][absent][late] != 0:\n",
    "                return memo[day][absent][late]\n",
    "            ans = 0\n",
    "            ans = (ans + dfs(day+1,absent,0)) % MOD\n",
    "            if absent < 1 :\n",
    "                ans = (ans + dfs(day+1,1,0)) % MOD\n",
    "            if late < 2:\n",
    "                ans = (ans + dfs(day+1,absent,late+1)) % MOD\n",
    "            memo[day][absent][late] = ans\n",
    "            return ans\n",
    "        return int(dfs(0,0,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def checkRecord(self, n: int) -> int:\r\n",
    "        M = 10 ** 9 + 7\r\n",
    "        # dp = [-1] * (n + 1)\r\n",
    "        # dp[0] = 1\r\n",
    "        # 对于只存在 L, P 的排列奖励\r\n",
    "        # def dp_cache(func):\r\n",
    "        #     def wrapper(i):\r\n",
    "        #         if i < 0:\r\n",
    "        #             return dp[0]\r\n",
    "        #         if dp[i] < 0:\r\n",
    "        #             dp[i] = func(i)\r\n",
    "        #         return dp[i]\r\n",
    "        #     return wrapper\r\n",
    "\r\n",
    "        @lru_cache(None)\r\n",
    "        def func(i):\r\n",
    "            if i <= 0 :\r\n",
    "                return 1\r\n",
    "            elif i == 1:\r\n",
    "                return 2\r\n",
    "            elif i == 2:\r\n",
    "                return 4\r\n",
    "            elif i == 3:\r\n",
    "                return 7\r\n",
    "            \r\n",
    "            return (2 * func(i-1) - func(i-4) ) % M\r\n",
    "\r\n",
    "        for i in range(n+1):\r\n",
    "            func(i)\r\n",
    "        # print(dp)\r\n",
    "        result = func(n)\r\n",
    "        for i in range(1, n+1):\r\n",
    "            result += (func(i-1) * func(n-i)) % M\r\n",
    "\r\n",
    "        return result % M\r\n",
    "\r\n",
    "# n = 2\r\n",
    "# n = 100\r\n",
    "# n = 100000\r\n",
    "# print(Solution().checkRecord(n))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            \n",
    "            flag = state & 1\n",
    "            ret = dfs(i + 1, flag | 2) #选p\n",
    "            if state & 4 == 0:\n",
    "                ret += dfs(i + 1, flag | 4) #选L\n",
    "                if i + 2 <= n:\n",
    "                    ret += dfs(i + 2, flag | 4) # 选LL\n",
    "            if not flag:\n",
    "                ret += dfs(i + 1, 1 | 8) # 选A\n",
    "            \n",
    "            return ret  % (10 ** 9 + 7)\n",
    "        \n",
    "        ret = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = pow(10, 9) + 7\n",
    "@cache\n",
    "def dfs (n, prel, prea):\n",
    "    if n == 1: return 1\n",
    "    ans = 0\n",
    "    if prel < 2:\n",
    "        ans += dfs(n - 1, prel + 1, prea)\n",
    "\n",
    "    if not prea:\n",
    "        ans += dfs(n - 1, 0, True)\n",
    "\n",
    "    ans += dfs(n - 1, 0, prea)\n",
    "\n",
    "    return ans % mod\n",
    "class Solution:\n",
    "    def checkRecord(self, n: int) -> int:\n",
    "        return (dfs(n, 0, False) + dfs(n, 1, False) + dfs(n, 0, True)) % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
